package leetcode.string;

import java.util.Arrays;

/**
 * 段式回文 其实与 一般回文 类似，只不过是最小的单位是 一段字符 而不是 单个字母。
 *
 * 举个例子，对于一般回文 "abcba" 是回文，而 "volvo" 不是，但如果我们把 "volvo" 分为 "vo"、"l"、"vo" 三段，则可以认为 “(vo)(l)(vo)” 是段式回文（分为 3 段）。
 *
 *  
 *
 * 给你一个字符串 text，在确保它满足段式回文的前提下，请你返回 段 的 最大数量 k。
 *
 * 如果段的最大数量为 k，那么存在满足以下条件的 a_1, a_2, ..., a_k：
 *
 * 每个 a_i 都是一个非空字符串；
 * 将这些字符串首位相连的结果 a_1 + a_2 + ... + a_k 和原始字符串 text 相同；
 * 对于所有1 <= i <= k，都有 a_i = a_{k+1 - i}。
 *  
 *
 * 示例 1：
 *
 * 输入：text = "ghiabcdefhelloadamhelloabcdefghi"
 * 输出：7
 * 解释：我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。
 * 示例 2：
 *
 * 输入：text = "merchant"
 * 输出：1
 * 解释：我们可以把字符串拆分成 "(merchant)"。
 * 示例 3：
 *
 * 输入：text = "antaprezatepzapreanta"
 * 输出：11
 * 解释：我们可以把字符串拆分成 "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)"。
 * 示例 4：
 *
 * 输入：text = "aaa"
 * 输出：3
 * 解释：我们可以把字符串拆分成 "(a)(a)(a)"。
 *  
 *
 * 提示：
 *
 * text 仅由小写英文字符组成。
 * 1 <= text.length <= 1000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-chunked-palindrome-decomposition
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class difficult_段式回文 {
    static class Solution {

        /**
         *
         * dp[:i]表示 0-i 有几个段氏回文 如果 为-1 则表示不成立回文
         */
        public int longestDecomposition(String text) {
            if (text.length() < 2) return 1;
            char[] textChars = text.toCharArray();
            int[] dp = new int[textChars.length/2];
            if (check(textChars, 0, 1)) dp[0] = 1;
            int n = 0;
            for (int i = 1; i < textChars.length/2; i++){
                for (int j = i-1; j >= 0; j--){
                    if (dp[j] > 0){
                        if (check(textChars, j+1, i-j)){
                            dp[i] = dp[j] + 1;
                            n = i;
                            break;
                        }
                    }
                    if (j == 0){
                        // 全部遍历完
                        if (check(textChars, 0, i+1)) {dp[i] = 1; n = i;}
                    }
                }
            }
            return Math.max(1, dp[n]*2 + ((textChars.length==(n+1)*2) ? 0 : 1));
        }


        private boolean check(char[] text, int start, int len){
            for (int i = 0; i < len; i++){
                if (text[start+i] != text[text.length-start-len+i]) return false;
            }
            return true;
        }
    }

    public static void main(String[] args){
        Solution s = new Solution();
        System.out.println(s.longestDecomposition("a"));
    }
}
